package com.zgkxzx.数据结构.哈希表;

/**
 * 创建者   zgkxzx
 * 创建日期 2018/5/5.
 * 功能描述
 * - 链地址法
 * 也是我们常用的HashMap结构
 */
public class HashLinkedTable<T> {

    private int size;

    private HashLinkedEntity hashArrayTableEntitys[];


    public HashLinkedTable(int size) {
        this.size = size;
        hashArrayTableEntitys = new HashLinkedEntity[size];
    }

    /**
     * 得到hash值
     *
     * @param key
     * @return
     */
    private int getHashCode(int key) {
        return (key & 0xfffff) % size;
    }

    /**
     * 插入值
     *
     * @param hashEntity
     */
    public void put(HashLinkedEntity<T> hashEntity) {
        if (hashEntity == null)
            return;
        //拿到Key
        int key = hashEntity.key;
        //hash变换后
        int hashCode = getHashCode(key);

        HashLinkedEntity hashLinkedEntity = hashArrayTableEntitys[hashCode];

        if (hashLinkedEntity == null)
            hashArrayTableEntitys[hashCode] = hashEntity;
        else {
            while (hashLinkedEntity != null && hashLinkedEntity.key != -1) {
                if (hashLinkedEntity.next == null) {
                    hashLinkedEntity.next = hashEntity;
                    return;
                } else
                    hashLinkedEntity = hashLinkedEntity.next;
            }

        }

    }

    public void put(int key, T value) {
        put(new HashLinkedEntity<T>(key, value));
    }

    /**
     * 获取摸个值
     *
     * @param key
     * @return
     */
    public HashLinkedEntity<T> getEntity(int key) {
        //hash变换后
        int hashCode = getHashCode(key);

        HashLinkedEntity hashLinkedEntity = hashArrayTableEntitys[hashCode];

        while (hashLinkedEntity != null && hashLinkedEntity.key != key) {
            hashLinkedEntity = hashLinkedEntity.next;
        }

        return hashLinkedEntity;
    }

    public T get(int key) {
        return getEntity(key) == null ? null : getEntity(key).value;
    }


    public void print() {
        for (int i = 0; i < hashArrayTableEntitys.length; i++) {
            //System.out.print(i + " --> " + hashArrayTableEntitys[i]);
            HashLinkedEntity hashLinkedEntity = hashArrayTableEntitys[i];
            while (hashLinkedEntity != null) {
                System.out.print("--> " + i + " --> " + hashLinkedEntity);
                hashLinkedEntity = hashLinkedEntity.next;
            }

            System.out.println();
        }
    }


    /**
     * 定义hash实体
     */
    public static class HashLinkedEntity<T> {
        public int key = -1;
        public T value;

        public HashLinkedEntity next;

        public HashLinkedEntity(int key, T value) {
            this.key = key;
            this.value = value;
        }


        @Override
        public String toString() {
            return "HashLinkedEntity{" +
                    "key=" + key +
                    ", value=" + value +
                    ", next=" + next +
                    '}';
        }
    }

}
